1. Field of the Invention
The present invention is related to a method and apparatus for controlling traffic in an internetwork. In particular, the present invention is related to a method and apparatus for server load balancing based on a hashing function.
2. Description of the Related Art
The growth of the Internet has caused problems unanticipated in its original design. As new users (clients) connect to the Internet. For example, to access servers for e-commerce, financial transactions, and intranet applications, the load on the servers has greatly increased. As the number of clients that access a server increase, the number of data packets processed by the server also increases. This increased load on the server may result in communications between clients and the server slowing down or timing out.
To solve this problem, the processing capability of the server may be increased, or a server with increased processing capacity may replace the old server. Ultimately, as shown in FIG. 1, additional servers 106–108, may be added to form a cluster of servers or server bank 110 to respond to the needs of clients. The server bank 110 provides a plurality of servers, each with the same content. Users, therefore, may connect to any one of the servers to access desired information. As can be seen, however, it is desirable to balance the demand, or load, placed on any one server, so that the resources of the server bank are effectively utilized. To that end, a Server Load Balancing (SLB) algorithm may be employed at router 105 wherein sessions from any one of clients 101-n are connected to a particular server in the server bank. The term clients, as used herein is construed to mean personal computers, wireless devices etc. that may be used to communicate with a server. As examples, a round robin algorithm, or a least connections algorithm is employed by a SLB algorithm to direct communications to one of a plurality of servers in the server bank.
With reference to FIG. 2, a SLB address table 200 may be maintained in router 105 to facilitate connections between clients and a server in the server bank. The SLB address table maintains information, in particular, address information for each server in the server bank, and each client that accesses the server bank, and maintains a mapping or binding between a particular client and server. This facilitates maintaining “sticky connections” between the server and client. A sticky connection is a connection wherein the same client communicates with the same server across multiple connection requests. For example, during multiple Transmission Control Protocol (TCP) (see RFC 793 and 879 for details on TCP) connection requests, a user accesses multiple related web pages during the filling out of a multi-page form using HyperText Transfer Protocol (HTTP) (see RFC 1945 for details on HTTP). The SLB address table contains an entry for each TCP connection comprising the Internet Protocol (IP) address of the client (source), and the server (destination), and the TCP port numbers of the client and server. When a data packet arrives at router 105 from a client, the router looks up in the SLB address table for an entry for a connection between the client and a server in the server bank. If there is a connection, the data packet is forwarded to the server in the server bank identified by the server IP address specified in the entry. However, if an entry does not exist in the SLB address table, a server is mapped to the client based on, for example, a round robin or least connections algorithm, and an entry corresponding to the connection is made in the SLB address table.
Subsequent data packets from a particular client connection are routed to the allocated server in the server bank by the router after performing a look up in the SLB address table as disclosed above. With numerous data packets from different clients, the router looks up the appropriate server's IP address in the SLB address table for each data packet received. With a large number of client connections, the size of the SLB address table can become very large, and a considerable amount of processing overhead is incurred by the router in searching the table for the address of the server prior to forwarding each data packet. As shown in FIG. 2, for ‘n’ clients, the router may have to search through at least ‘n’ rows of data for a server's IP address. This process is time consuming, inefficient and may require considerable memory to store the SLB address table. What is needed, therefore, is a more efficient way to balance traffic load among a plurality of servers.